1. Field of the Invention
The present invention relates generally to loop detection in publish and subscribe (pub/sub) networks and like message-passing networks. More particularly, the present invention relates to topic-based loop detection in publish/subscribe networks.
2. Description of the Prior Art
In a publish/subscribe network, any number of consumers (e.g., computers; clients) can receive messages that are provided by one or more producers (e.g., computers; servers). In this case, a producer is called a publisher and a consumer is called a subscriber.
A publish/subscribe network operates based on a topic on which any number of interested consumers can subscribe in order to register their interest. This is similar to the way that a person might subscribe only to magazines about topics in which they are interested. Each topic provides particular event or state information. A topic is also a sub-section of a topic space (i.e., a composition of a hierarchy of topics), which is specifically marked as able to forward publications and subscriptions from producers to consumers.
A publisher can send messages (e.g., publications) containing information about a particular topic to all subscribers to that topic, without any knowledge of how many subscribers there are, or the details of the nodes that host those subscribers. In this way, publish/subscribe network completely decouples the provider of the information from the consumer of that information.
In order to facilitate this publish/subscribe network, a broker is required to hold information about which subscribers have subscribed to which topics and how to deliver messages to them. A publisher can then publish messages using the broker to all subscribers on that topic without knowing the details of those subscribers. There can be multiple publishers for a particular topic, and a subscriber to information about one topic can also be a publisher of information about other topics.
The broker is a component to which client applications connect to perform publish and subscribe messages in the publish/subscribe network. The broker handles the matching of publications with subscriptions, the distribution of publications to subscribing applications, and the persistence of messages to ensure a message delivery at the quality of service required. The broker acts as a hub for routing messages between publishers and subscribers. The broker can store messages on behalf of a client (i.e., a publisher or a subscriber) that is not connected and make them available to the client when it reconnects. Therefore, a broker can be understood as a data processing system in a publish/subscribe network. Brokers are connected to the publish/subscribe network as nodes.
When constructing a network of connected pub/sub (publisher/subscriber) brokers, it is essential that publications do not enter a loop (i.e., a closed circuit of links between brokers). Therefore, necessary mechanisms need to be implemented to prevent any one publication from looping indefinitely. Without any form of loop detection, publications can perpetually loop through a set of pub/sub brokers, causing subscribers to receive many duplicate publications while the publication loops perpetually. In addition, the loop will result in the network becoming overwhelmed by publications that cannot be removed.
Numerous prior art solutions exist for detecting and/or preventing occurrence of loops in networks. For example, Dawson et al. (U.S. Pat. No. 6,230,198) discloses a server-to-server event message generated for a received event. The server-to-server event message includes an event identifier, a text pertinent to event message, and a source trail indicating the origin and history of the event. The source trail comprises any source trail from a sending server received with the event, the identifier of the client supplying event, and an identifier of the present server. The server-to-server event message is then transmitted to the receiving server, so that the receiving server may know the origin and any subsequently transmitting servers in the distribution. The source trail of the server-to-server event message can be parsed to determine each identifier in the source trail. The server-to-server event message is transmitted to the receiving server only if the receiving server identifier is absent from the parsed source trail, thus preventing any loops, which might cause the event to be repeatedly received.
Benedict et al. (U.S. Pat. No. 5,321,812) discloses generating a loop-detection message. There is a risk that the brokers will become configured into a closed loop within which data will circulated endlessly. To eliminate this risk, a loop-detection message is generated when a broker acquires a new server broker and is itself a server broker for other brokers. The message, which includes the originating broker's name, is passed from served broker to server broker. Each broker inspects the message. If it does not find its own name, it appends its name to the message and passes it on to its own server broker. If the broker does find its own name, it generates a loop-detected message that revokes the server/served relationship with the current server broker.
However, these prior solutions require maintaining knowledge of the whole network configuration. Maintaining knowledge of whole network configuration at each broker introduces a significant overhead in large networks and breaks the concept that each broker should only be aware of directly connected brokers. In addition, topic space (i.e., a composition of a hierarchy of topics) becomes confined to the connection network.
Therefore, there is a need for a loop detection system/method which takes place during the pub/sub network configuration stage, to prevent excessive overhead during normal operation. It would be desirable to provide a loop detection system/method that enables a broker to only require knowledge of directly connected brokers, and that is capable of permitting connection loops if a topic space is appropriately configured to prevent any publications looping back to their point of origin.